#!/usr/bin/env python3

"""
Given two non-empty linked lists representing two non-negative integers. 
The digits are stored in reverse order, and each of their nodes contain a single digit. 

Add the two numbers and return it as a linked list:

Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def compose(self, next):
        self.next = next
        return next

    def print(self, title=''):
        print(f'{title} {self.val}', end=' ')
        if self.next:
            self.next.print()


def add_two_numbers(left, right):
    result = None
    current = None
    add_one = 0
    while left is not None or right is not None:
        left_val = left.val if left else 0
        right_val = right.val if right else 0
        val = left_val + right_val + add_one
        if val >= 10:
            val -= 10
            add_one = 1
        else:
            add_one = 0

        node = ListNode(val)
        if current:
            current.compose(node)
        else:
            result = node
        current = node
        if left:
            left = left.next
        if right:
            right = right.next
    if add_one == 1:
        current.compose(ListNode(1))
    return result

if __name__ == '__main__':
    left = ListNode(2)
    left.compose(ListNode(4)).compose(ListNode(3))
    left.print("LinkedList")
    print()
    right = ListNode(5)
    right.compose(ListNode(6)).compose(ListNode(4))
    result = add_two_numbers(left, right)
    result.print()
    print()
